home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 2 / Amiga Tools 2.iso / tex / macros / source / packages / epic / picman.tex / node16_mn.html < prev    next >
Text File  |  1995-03-15  |  8KB  |  173 lines
  1.  
  2. <H2><A ID="SECTION00070000000000000000">
  3. References</A>
  4. </H2><tex2html_bbl_mark>#1#
  5.  
  6. <P>
  7.  
  8.  
  9. <P><BR>
  10.  
  11. <#376#><FONT SIZE="+2"><B>Appendix A   Estimating Pythagorean Square-root</B></FONT><#376#>
  12.  
  13. <P>
  14.  
  15. <P><BR>
  16.  
  17. For the line drawing commands described in the main sections of this
  18. document, we need to estimate the Pythagorean square-root in order to
  19. determine the length of the line (along its slope). More precisely, we need
  20. to estimate the number of segments of a given length needed to draw a line.
  21. T<SMALL>E</SMALL>X does not provide for floating point calculations, and thus there are no
  22. direct means of calculating the above square-root. Most standard numerical
  23. techniques are iterative and would be too slow when used with T<SMALL>E</SMALL>X for lack
  24. of floating point calculations, and in particular, real division, since
  25. calculation of such a square-root is needed very frequently.
  26.  
  27. <P>
  28. A simple non-iterative formula for estimating the square-root is derived and
  29. described below.
  30.  
  31. <P>
  32.  
  33. <P><P><BR>
  34.  
  35. <#377#><B>Problem: </B><#377#> Given <I>a</I> and <I>b</I>, to find <I>c</I> = <tex2html_verbatim_mark>#math95#<tex2html_image_mark>#tex2html_wrap_inline1741# using
  36. only operations in {+ , - ,*,/}.
  37.  
  38. <P>
  39. We can get very tight bounds on the square-root as follows.
  40. Without loss of generality, let <I>a</I>≥<I>b</I>. We seek a simple <I>n</I>
  41. such that:
  42. <P><tex2html_verbatim_mark>#math96#</P><DIV ALIGN="CENTER">
  43. <tex2html_image_mark>#tex2html_wrap_indisplay1746#≥<I>a</I> + <tex2html_image_mark>#tex2html_wrap_indisplay1747#
  44. </DIV><P></P>
  45.  
  46. <P>
  47. Squaring both sides, we have
  48. <P><tex2html_verbatim_mark>#math97#</P><DIV ALIGN="CENTER">
  49. <TABLE>
  50. <TR VALIGN="MIDDLE"><TD ALIGN="LEFT">⇔</TD>
  51. <TD ALIGN="RIGHT"><I>a</I><SUP>2</SUP> + <I>b</I><SUP>2</SUP></TD>
  52. <TD ALIGN="CENTER">≥</TD>
  53. <TD ALIGN="LEFT"><I>a</I><SUP>2</SUP> + <tex2html_image_mark>#tex2html_wrap_indisplay1753# + <tex2html_image_mark>#tex2html_wrap_indisplay1754#</TD>
  54. </TR>
  55. <TR VALIGN="MIDDLE"><TD ALIGN="LEFT">⇔</TD>
  56. <TD ALIGN="RIGHT">(1 - <tex2html_image_mark>#tex2html_wrap_indisplay1757#)<I>b</I><SUP>2</SUP></TD>
  57. <TD ALIGN="CENTER">≥</TD>
  58. <TD ALIGN="LEFT"><tex2html_image_mark>#tex2html_wrap_indisplay1760#</TD>
  59. </TR>
  60. <TR VALIGN="MIDDLE"><TD ALIGN="LEFT">⇔</TD>
  61. <TD ALIGN="RIGHT"><tex2html_image_mark>#tex2html_wrap_indisplay1763#</TD>
  62. <TD ALIGN="CENTER">≥</TD>
  63. <TD ALIGN="LEFT"><tex2html_image_mark>#tex2html_wrap_indisplay1766#</TD>
  64. </TR>
  65. <TR VALIGN="MIDDLE"><TD ALIGN="LEFT"><#1#>or <#1#></TD>
  66. <TD ALIGN="RIGHT">(<tex2html_image_mark>#tex2html_wrap_indisplay1769#)<I>n</I><SUP>2</SUP> -2<I>n</I> - (<tex2html_image_mark>#tex2html_wrap_indisplay1770#)</TD>
  67. <TD ALIGN="CENTER">≥</TD>
  68. <TD ALIGN="LEFT">0</TD>
  69. </TR>
  70. </TABLE>
  71. </DIV><P></P>
  72.  
  73. <P>
  74. ;SPMgt;From the quadratic equation above, we finally get an expression for <I>n</I>,
  75. <P><tex2html_verbatim_mark>#math98#</P><DIV ALIGN="CENTER">
  76. <I>n</I>   =  <tex2html_image_mark>#tex2html_wrap_indisplay1775#   =  <tex2html_image_mark>#tex2html_wrap_indisplay1776#
  77. </DIV><P></P>
  78.  
  79. <P>
  80. Only the +ve root interests us since <I>n</I> has to be positive.
  81. Note that the term under the root is  bounded above and below (since
  82. <tex2html_verbatim_mark>#math99#<tex2html_image_mark>#tex2html_wrap_inline1780#≤1):
  83. <P><tex2html_verbatim_mark>#math100#</P><DIV ALIGN="CENTER">
  84. 1  ≤  <tex2html_image_mark>#tex2html_wrap_indisplay1782#  ≤  <tex2html_image_mark>#tex2html_wrap_indisplay1783#
  85. </DIV><P></P>
  86.  
  87. <P>
  88. Hence, we have two values for <I>n</I>,
  89. <P><tex2html_verbatim_mark>#math101#</P><DIV ALIGN="CENTER">
  90. <I>n</I><SUB>l</SUB>   =  <tex2html_image_mark>#tex2html_wrap_indisplay1786#   =  <tex2html_image_mark>#tex2html_wrap_indisplay1787#;                    <I>n</I><SUB>u</SUB>   =  <tex2html_image_mark>#tex2html_wrap_indisplay1788#   =  <tex2html_image_mark>#tex2html_wrap_indisplay1789#
  91. </DIV><P></P>
  92. which finally gives us a lower and an upper bound for <I>c</I>, the Pythagorean
  93. square-root,
  94. <P><tex2html_verbatim_mark>#math102#</P><DIV ALIGN="CENTER">
  95. <I>a</I> + <tex2html_image_mark>#tex2html_wrap_indisplay1792#  ≤  <I>c</I>  ≤  <I>a</I> + <tex2html_image_mark>#tex2html_wrap_indisplay1793#
  96. </DIV><P></P>
  97.  
  98. <P>
  99. These are very tight bounds. Denoting the lower bound as <I>c</I><SUB>l</SUB> and upper
  100. one <I>c</I><SUB>u</SUB>, below are some numerical results (<I>c</I> = exact square-root):
  101.  
  102. <P>
  103. <DIV class="CENTER">
  104. <TABLE CELLPADDING=3 BORDER="1">
  105. <TR><TD ALIGN="CENTER">a</TD>
  106. <TD ALIGN="CENTER">b</TD>
  107. <TD ALIGN="CENTER">c</TD>
  108. <TD ALIGN="CENTER"><I>c</I><SUB>l</SUB></TD>
  109. <TD ALIGN="CENTER"><I>c</I><SUB>u</SUB></TD>
  110. </TR>
  111. <TR><TD ALIGN="CENTER">100.0</TD>
  112. <TD ALIGN="CENTER">100.0</TD>
  113. <TD ALIGN="CENTER">141.4213</TD>
  114. <TD ALIGN="CENTER">141.4213</TD>
  115. <TD ALIGN="CENTER">150.0</TD>
  116. </TR>
  117. <TR><TD ALIGN="CENTER">100.0</TD>
  118. <TD ALIGN="CENTER">;SPMnbsp;80.0</TD>
  119. <TD ALIGN="CENTER">128.0642</TD>
  120. <TD ALIGN="CENTER">126.5096</TD>
  121. <TD ALIGN="CENTER">132.0</TD>
  122. </TR>
  123. <TR><TD ALIGN="CENTER">;SPMnbsp;30.0</TD>
  124. <TD ALIGN="CENTER">;SPMnbsp;20.0</TD>
  125. <TD ALIGN="CENTER">;SPMnbsp;36.0555</TD>
  126. <TD ALIGN="CENTER">35.5228</TD>
  127. <TD ALIGN="CENTER">36.6667</TD>
  128. </TR>
  129. </TABLE>
  130. </DIV>
  131.  
  132. <P>
  133. With the above bounds, one can do a linear interpolation to get exact values.
  134. In our case, since it is not required to be <#434#><I>extremely</I><#434#> accurate, for 
  135. estimating the square-root in the line drawing commands,
  136. we simply take the midpoint of the two bounds. For small
  137. numbers, which is expected to be the case most of the time,
  138. the error is very small.
  139.  
  140. <P>
  141. With some algebra, we get the mid-point estimate of <I>c</I>,
  142. <P><tex2html_verbatim_mark>#math103#</P><DIV ALIGN="CENTER">
  143. <I>c</I> = <tex2html_image_mark>#tex2html_wrap_indisplay1821# = <I>a</I> + <tex2html_image_mark>#tex2html_wrap_indisplay1822# = <I>a</I> + <tex2html_image_mark>#tex2html_wrap_indisplay1823#        (<I>a</I>≥<I>b</I>)
  144. </DIV><P></P>
  145.  
  146. <P>
  147. The macro <tex2html_verb_mark>144<tex2html_verb_mark> uses the above formula for estimating the
  148. number of points (for <tex2html_verb_mark>145<tex2html_verb_mark> macro) and number of segments (for
  149. <tex2html_verb_mark>146<tex2html_verb_mark> macro). The <tex2html_verb_mark>147<tex2html_verb_mark> macro, instead of
  150. calculating the length of the line, directly calculates the <#441#><I>number</I><#441#> of
  151. segments of a given length. For example, to draw a dotted line from
  152. (<I>x</I><SUB>1</SUB>, <I>y</I><SUB>1</SUB>) to (<I>x</I><SUB>2</SUB>, <I>y</I><SUB>2</SUB>) with the inter-dot-gap as <I>d</I>, we estimate the
  153. number of dots <I>n</I> using the following expression,
  154. <P><tex2html_verbatim_mark>#math104#</P><DIV ALIGN="CENTER">
  155. <I>n</I> = <tex2html_image_mark>#tex2html_wrap_indisplay1829# + <tex2html_image_mark>#tex2html_wrap_indisplay1830#              <I>Δx</I> = | <I>x</I><SUB>2</SUB> - <I>x</I><SUB>1</SUB>|<#1#> and <#1#><I>Δy</I> = | <I>y</I><SUB>2</SUB> - <I>y</I><SUB>1</SUB>|
  156. </DIV><P></P>
  157. assuming <tex2html_verbatim_mark>#math105#<I>Δx</I>≥<I>Δy</I> (otherwise they may be inter-changed).
  158.  
  159. <P>
  160. Note that since divisions in T<SMALL>E</SMALL>X are integer-divisions, it is simpler to
  161. deal in ``number of segments'' rather than actual lengths
  162. (e.g. in the expression above, <tex2html_verbatim_mark>#math106#<tex2html_image_mark>#tex2html_wrap_inline1833# = number of segments
  163. along X-axis).
  164.  
  165. <P>
  166.  
  167. <#451#><B>Caveat:</B><#451#> The approach presented here for estimation of
  168. Pythagorean square-root is an independent effort by the author. It may
  169. already exist in the literature --- the author is neither aware of it nor has
  170. he made any serious attempts at uncovering it.
  171.  
  172. <P>
  173.